package com.cty.B_SpecialDataStructures.C_PriorityQ.PriorityQHeap;

import com.cty.F_common.DataItem;

/**
 * @Auther: cty
 * @Date: 2020/6/15 0:04
 * @Description: 数组实现堆
 * 重要操作：
 *      ① insertFirst(DataItem): void    O(1)
 *      ② deleteFirst(): DataItem    O(1)
 *      ③ insertLast(DataItem): void    O(1)
 * @version: 1.0
 */
public class HeapArray {
    private int maxSize;
    private DataItem[] array;
    private int nItems;

    public HeapArray(int maxSize){
        this.maxSize = maxSize;
        array = new DataItem[maxSize];
        nItems = 0;
    }

    public boolean isEmpty(){
        return (nItems == 0);
    }

    public boolean isFull(){
        return (nItems == maxSize);
    }

    public int size(){
        return nItems;
    }

    public void displayArray(){
        for(int i=0; i<nItems; i++)
            System.out.print(array[i].getKey() + " ");
        System.out.println();
    }

    /**
     * 插入  O(logN)
     *      尾部插入，向上筛选
     * @param item
     * @return
     */
    public boolean insert(DataItem item){
        if(isFull())
            return false;

        array[nItems] = item;
        trickleUp(nItems++);
        return true;
    }  // end insert()

    /**
     * 删除  O(logN)
     *      头部删除，向下筛选
     * @return
     */
    public DataItem remove(){
        if(isEmpty())
            return null;

        DataItem temp = array[0];
        array[0] = array[--nItems];
        trickleDown(0);
        return temp;
    }  // end remove()

    /**
     * 改变指定索引位置处数据项的关键字  O(logN)
     * @param index
     * @param newKey
     * @return
     */
    public boolean change(int index, long newKey){
        if(index<0 || index>=nItems)
            return false;

        long oldKey = array[index].getKey();
        array[index].setKey(newKey);

        if(newKey > oldKey)
            trickleUp(index);
        else
            trickleDown(index);
        return true;
    }  // end change()

    /**
     * 向上筛选  O(logN)
     * @param index
     */
    public void trickleUp(int index){
        DataItem temp = array[index];  // 记录待交换处数据
        int parent = (index - 1) / 2;

        while(index > 0 && temp.getKey() > array[parent].getKey()){
            array[index] = array[parent];  // 父节点下移
            index = parent;  // 移动到父节点
            parent = (index - 1) / 2;  // 获取新的父节点
        }
        array[index] = temp;
    }  // end trickleUp()

    /**
     * 向下筛选  O(logN)
     * @param index
     */
    public void trickleDown(int index){
        DataItem temp = array[index];  // 记录待交换数据
        int largeChild;

        while(index < (nItems/2)){  // 至少有一个左节点
            // 选出最大子节点
            int leftChild = 2*index + 1;
            int rightChild = leftChild + 1;
            if(rightChild < nItems && array[rightChild].getKey() > array[leftChild].getKey())
                largeChild = rightChild;
            else
                largeChild = leftChild;

            // 当大于等于最大子节点关键字时退出循环
            if(temp.getKey() >= array[largeChild].getKey())
                break;

            // 否则交换并更新循环条件
            array[index] = array[largeChild];
            index = largeChild;
        }  // end while
        array[index] = temp;
    }  // end trickleDown()


}  // end HeapArray{}
